1. Field of the Invention
The present invention relates to FIFO buffers generally, and more specifically, to a high speed asynchronous and programmable state machine configured to generate Almost Empty synchronous flags in a synchronous FIFO buffer.
2. Discussion of the Prior Art
A FIFO is a two-port memory based on dual-ported RAM cells. One port is used for writing data into the memory, while the other port is used for reading data out. A memory location in a FIFO is written to and is read from simultaneously, and a FIFO""s first-in/first-out architecture or device, defines the method for storing and retrieving data from memory: data is written into a FIFO at one value at a time, and is read from the device in the same order as it was written in.
A FIFO doesn""t require an address to access data, unlike RAM, or read-only memories (ROM). Another difference between a FIFO and a RAM, or ROM, is the data retention: in a RAM or ROM, data at a particular address remains unchanged until another value is written into the memory, and reading a data value out does not change the data value stored at a particular address. In a FIFO, data written into the memory is retained until it is read out. However, once the data word is read out, it no longer exists in the memory and cannot be accessed again. The exception is a FIFO that has a retransmit feature. The retransmission feature allows for a segment of a FIFO""s memory to be read many times, although the data is written into the FIFO only once.
Due to the nature of their data retention, a FIFO (without a retransmission feature) has a state of xe2x80x9cData Fullnessxe2x80x9d associated with it. More specifically, a FIFO can be Empty, Almost Empty, partially Empty, partially Full, Almost Full, and Full. Thus, a FIFO requires additional signal lines, or flags, to indicate the state of its memory content. The number of data words a FIFO can store before it is Full depends on its size.
Because of a FIFO""s unique features, like the lack of addressing requirements, FIFOs are useful in a class of applications with a serial streams of data. A FIFO provides data at the read port in the same order the data was presented at the write port, so that no additional circuitry is needed to implement a store-and-forward buffer. In the store-and-forward buffer, the data is written into the FIFO by a high-speed data source and is read out onto a lower-speed data bus. Thus, the FIFO converts the data rate from a high speed to a lower speed without any specific relationship between its input and output data rates. This means that a FIFO can serve as a link between two asynchronous interfaces.
While a random-access memories (RAM) can perform write and read operations only sequentially, a FIFO can do these operations simultaneously. Thus, a FIFO has twice the throughput of a conventional RAM. When its shift-in and shift-out signals are derived from independent frequency sources, a FIFO is operating asynchronously. If this is the case, the relationship between the output system clock and an output-ready signal is not known, either with respect to frequency, or with respect to phase.
However, when its shift-in and shift-out signals are derived from a common frequency source or clock, so that there is a precise, known relationship between them- the FIFO is by definition is in the synchronous mode. The key advantages of the synchronous FIFO over the asynchronous FIFO, are as follows:
(A) Registered interfaces at the input and output provide the simplest and fastest FIFO interfacing because all signals are synchronized to the rising edges of the read or write system clocks, which run continuously and are applied directly to the FIFO;
(B) Read and write operations are easily manipulated by external, synchronous read and write state machines, which in turn are controlled by the read and write system clocks; the flags are internally synchronized to their respective clocks, and external synchronizers are no longer needed;
(C) Read and write operations are controlled by enables, thereby eliminating any need for externally-generated read and write strobes; noise immunity is improved because the enable signals are sampled during the rising edge of the clock rather than in response to a level, thus increasing the reliability.
Accordingly, the following discussion is focused on synchronous FIFOs. Typical FIFO includes a 64 Kbit depth and 80 bits width, whereas the word is typically 80 bits long. One pointer, read or write, points to only one word. However, the xe2x80x9cread outxe2x80x9d or xe2x80x9cwrite inxe2x80x9d operations can be implemented in 4 modes: (a) read out 80-mode, (b) write in 80-mode (at each clock the whole word is read out or written in), (c) read out 40-mode, and (d) write in 40-mode (at each two clocks the whole word is read out or written in).
The number of words N retained in the FIFO memory is as follows:
N=Wxe2x88x92R;xe2x80x83xe2x80x83(1)
wherein W is the number of words written into the memory; and R is the number of words that are read out from the memory.
To prevent a xe2x80x9ctoo fastxe2x80x9d read out, a read enables clock is activated only after a first word is written into the FIFO memory buffer. Thus, the read out operation has to wait depending on the particular FIFO device between (2-4) clocks before the first word is read out. For the second word there is no such limitation. Each time a FIFO is completely read out, an Empty flag is generated by a state machine. An enabling signal delays the generation of an Empty flag, that is the change of the Empty flag state from xe2x80x9czeroxe2x80x9d to xe2x80x9cone is delayed, by a waiting period between (2-4) clocks needed for the first word to be read out. This prevents reading out a word that has not been written in yet. The reading out of a word before the word has been written is called underflow. The time needed for the first word to come out from the FIFO buffer is called the fall through time.
For the complementary situation, when the writing in is done very fast, and the read out is very slow, a FIFO can be filled over capacity. This situation is called overflow. To prevent the overflow from happening, the Full flag is generated by the enabling Full signal to indicate that the writing into the FIFO should stop before the first word is read out.
The prior art xe2x80x9cAlmostxe2x80x9d Empty flags were used to indicate that only few words X are left in the FIFO buffer. Thus, an offset X defining the word xe2x80x9cAlmostxe2x80x9d, is also an xe2x80x9cAlmost Emptyxe2x80x9d threshold. The Almost Empty offset, or threshold, X is a user programmable offset. The user can set an offset value X anywhere between Full and Empty so that if the number of words N left in a FIFO is less than the threshold X, the read out is impossible, and an Almost Empty Flag is generated:
If ((N=Wxe2x88x92R)xe2x89xa6X) then Almost_Emptyxe2x80x94N=0;xe2x80x83xe2x80x83(2)
wherein W is the number of words that are written in, R is the number of words that are read out, and Almost_Empty_N is a read pointer.
Complementary, if the programmable threshold for the amount of memory space (measured in words) left is Y, and if the actual memory space left in a FIFO is less than the threshold Y, the write in to the FIFO is restricted, and an Almost Full flag is generated:
xe2x80x83If (((Depthxe2x88x92(Wxe2x88x92R))xe2x89xa6Y) then Almost_Fullxe2x80x94N=0;xe2x80x83xe2x80x83(3)
wherein Depth is the depth of the FIFO, W is the number of words that are written in, R is the number of words that are read out, and Almost_Full_N is a write pointer.
The prior art implementation of the Almost Empty and Almost Full flag generators was done by using a traditional xe2x80x9cadder approachxe2x80x9d. In this traditional xe2x80x9cadder approachxe2x80x9d, the relationship (2) and /or (3) are implemented by using a write counter, a read counter, a program value offset register, a triple input carry look ahead adder/comparator (including a prediction algorithm to predict the next value), and an adder glitch filter (to minimize noise).
The problem with this prior art xe2x80x9cadder approachxe2x80x9d is that the triple input carry look ahead adder/comparator is too slow because in order to do additions and comparisons, the prior art adder circuitry requires 6 nsec.
What is needed is to implement the relationship (2) and (3) without an adder in order to significantly reduce the time required for this operation.
The present invention provides a high speed asynchronous and programmable state machine utilized for generating Almost Empty synchronous flags in a synchronous FIFO. The present invention uses a xe2x80x9cstate machine approachxe2x80x9d and eliminates an adder altogether. In the present xe2x80x9cstate machine approachxe2x80x9d a look ahead signal is generated when the following logical statements reach the true value:
If (W==(R+X)), then look ahead_signal=1;xe2x80x83xe2x80x83(4)
and/or
If (W==R+Depthxe2x88x92(Y+1)), then lookaheadxe2x80x94signal=1.xe2x80x83xe2x80x83(5)
X (and /or (Y+1)) offset are pre-loaded into the read pointer, the write pointer is reset to xe2x80x9c0xe2x80x9d, and only a comparator is required to check the xe2x80x98truexe2x80x99 or xe2x80x98falsexe2x80x99 value of the logical statement (4) (and /or (5)) thus significantly reducing the time required for this operation as compared with the prior art xe2x80x9cadderxe2x80x9d approach for generating Almost Empty flags.
More specifically, one aspect of the present invention is directed to a state machine. In one embodiment, the state machine comprises: (1) a first input receiving a first write clock, (2) a second input receiving a first read clock, (3) a third input receiving a first programmable Almost Empty look-ahead signal, (4) a fourth input receiving a second write clock, (5) a fifth input receiving a second read clock, and (6) a sixth input receiving a second programmable Almost Empty look-ahead signal. The state machine manipulates the inputs to produce an output signal representing an Almost Empty output flag that is at a first logic state when a FIFO is Almost Empty and is at a second logic state when the FIFO is Not Almost Empty.
Another aspect of the present invention is directed to an apparatus comprising: (1) a first set state machine having a first input receiving a first write clock, a second input receiving a first read clock, a third input receiving a first programmable Almost Empty look-ahead signal, and a fourth input to receive a first control signal; (2) a second set state machine having a first input receiving a second write clock, a second input receiving a second read clock, a third input receiving a second programmable Almost Empty look-ahead signal, and a fourth input to receive a second control signal; and (3) a synchronizer coupled to the second set state machine. The first set state machine manipulates its inputs to produce a first set_output signal that is either at a first logic state or at a second logic state, whereas the second set state machine manipulates its inputs to produce a second set_output signal that is either at the first logic state or at the second logic state. The synchronizer receives the second set_output signal and receiving a reset signal. The synchronizer is configured to generate a synchronized output signal.
The apparatus of the present invention further comprises: (4) a latch having a first input receiving the first set_output signal, and a second input receiving the synchronized output signal. A first latch_output presents the first set_output signal as a first latch_output signal, whereas a second latch_output presents the synchronized output signal as a second latch_output signal. The latch is configured to hold the first latch_output signal and the second latch_output signal until the first set_output signal and second set_output signal change logic states. The first latch_output signal represents an Almost Empty output flag that is at a first logic state when a FIFO memory block is Almost Empty, and is at a second lo logic state when the FIFO is Not Almost Empty. The second latch_output signal represents the Not Almost Empty output flag that is at the first logic state when the FIFO is Not Almost Empty and is at the second logic state when the FIFO is Almost Empty.
The apparatus of the present invention further comprises: (5) a first logic block having a logic input receiving the second latch_output signal, and (6) a second logic block having a logic input receiving the first latch_output signal. The first logic block includes a logic output presenting the second latch_output signal as the first control signal to the first set state machine; wherein the second logic block has a first logic output presenting the first latch_output signal as the second control signal to the second set state machine; and a second logic output presenting the first latch_output signal as the reset signal to the synchronizer.
In one embodiment of the present invention, the synchronizer further includes an SR latch coupled to the second set state machine. The SR latch is configured to receive the second set_output signal from the second set state machine, and the reset signal from the second logic block, and is configured to time an output of the second set_output signal depending on the reset signal. A Flip-Flop (FF) block coupled to the SR latch is configured to receive the second set_output signal, and configured to time the presentation of the second set_output signal as the synchronized signal depending on an external timing signal.
In the preferred embodiment, the FIFO comprises a synchronous FIFO; the external timing signal comprises a free running read clock signal; the first write clock comprises a first enabled write clock; the first read clock comprises a first enabled read clock; the second write clock comprises a second enabled write clock; and the second read clock includes a second enabled read clock.
In one embodiment, the apparatus of the present invention further comprises a first delay block configured to provide a first predetermined delay to the first set_output signal in order to increase a pulse width of the first set_output signal. In one embodiment, the apparatus of the present invention further comprises a second delay block configured to provide a second predetermined delay to the second set_output signal in order to increase a pulse width of the second set_output signal. In one embodiment, the first delay block further includes a first programmable delay block configured to change a pulse width of the first set_output signal. In one embodiment, the second delay block further includes a second programmable delay block configured to change a pulse width of the second set_output signal.
One more aspect of the present invention is directed to a method for determining the almost emptiness of at least one memory buffer. In one embodiment, the method of the present invention further comprises the following steps: (1) generating at least one Almost Empty output flag in response to a plurality of signals comprising: a first write clock, a first read clock, a first programmable Almost Empty look-ahead signal, a second write clock, a second read clock, and a second programmable Almost Empty look-ahead signal; (2) generating at least one Not Almost Empty output flag in response to a plurality of signals comprising: a first write clock, a first read clock, a first programmable Almost Empty look-ahead signal, a second write clock, a second read clock, and a second programmable Almost Empty look-ahead signal; and (3) presenting the first write clock, the first read clock, the first programmable Almost Empty look-ahead signal, the second write clock, the second read clock, and the second programmable Almost Empty look-ahead signal to a state machine.